Heapsort

Heapsort

 

[dt. »Sortierung von Haufen«], ein 1964 von James W. J. Williams entwickelter Algorithmus, mit dem beliebige Daten in auf- oder absteigender Reihenfolge sortiert werden. Er basiert auf dem 1962 von Robert W. Floyd veröffentlichten Treesort-Verfahren. Für die Heapsort-Sortierung werden die Daten zunächst in einem binären Baum dargestellt, dem »Heap-Baum«. Ein Heap-Baum ist binär und außerdem vollständig, d. h., er enthält mit Ausnahme der untersten Ebene keine Lücke. Zusätzlich soll der Baum noch geordnet sein, was allerdings erst durch die Sortierung gewährleistet wird. Programmintern erfolgt die Speicherung der Daten in Form eines Arrays.

 

Beginnend von unten nach oben und von links nach rechts werden die Daten nun paarweise so vertauscht, dass jedes an einem Knoten liegende Element größer ist als die beiden Elemente in den dort entspringenden Ästen. Sobald das größte Element an der Spitze des Baums steht, wird es aus dem Baum entfernt und durch das am weitesten rechts unten stehenden Element ersetzt. Das aussortierte Element wird in die (sortierte) Ergebnisliste eingetragen.

 

Die für eine Sortierung benötigte Zeit hängt wie n × log (n) von der Anzahl n der zu sortierenden Elemente ab. Damit gehört das Heapsort-Verfahren zu den schnellsten Sortieralgorithmen. Lediglich das Verfahren Quicksort, das spezielle Abbruchkriterien enthält, ist noch geringfügig schneller.